package com.liyghting.datastructurealgorithm.recursion;

import java.util.HashMap;
import java.util.Map;

/**
 * 递归 最终推荐人 DFS深度优先搜索 前中后序二叉树遍历
 *
 * @author LiYiGuang
 * @date 2020/1/9 16:47
 */
public class Recursion {
    private Map hasResolveMap;
    public Recursion() {
        this.hasResolveMap = new HashMap();
    }


	public int movieFloor(int n) {
		if (n == 1)
			return 1;
		return movieFloor(n - 1) + 1;
	}

    /**
     * n 个台阶，每次可以下一个台阶或者2个台阶，有多少种下法；
     * @param n
     * @return
     */
	public int floor(int n) {
		if (n == 1)
			return 1;
		if (n == 2)
			return 2;
        if (hasResolveMap.containsKey(n)) {
            return (int)hasResolveMap.get(n);
        }
        int ret = floor(n - 1) + floor(n - 2);
        hasResolveMap.put(n, ret);
		return ret;
	}



}
